package com.youth.day01;

/**
 *  堆排序
 * @author Jinx
 * @date 2021/6/13 2:55
 */
public class HeapSort {

    /**
     *  时间复杂度：O(n²)
     */
    public static int[] sort(int[] arr) {
        if (arr == null || arr.length < 1) {
            return arr;
        }

        int temp;
        // 外层 控制轮数
        for (int i = arr.length - 1; i > 0; i--) {
            // 从最后一个父节点开始
            for (int j = (i-1)/2; j >= 0; j--) {
                // 当前节点的左右子节点
                int left = 2 * j + 1;
                int right = 2 * j + 2;

                if(arr[j] < arr[left]){
                    temp = arr[j];
                    arr[j] = arr[left];
                    arr[left] = temp;
                }
                // 右子节点可能不在遍历范围
                if(right <= i && arr[j] < arr[right]){
                    temp = arr[j];
                    arr[j] = arr[right];
                    arr[right] = temp;
                }
            }

            // 头尾节点交互位置
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
        }

        return arr;
    }
}
